class XFS():
    move_method = [(-1,0),(1,0),(0,-1),(0,1)]
    start = -1
    end = 2
    access = 0
    block = 1
    open_table = []
    closed_table = []

                    
    def __init__(self,X,puzzle,width,height):
        self.X = 0 if X == 'B' else -1 if X=='D' else -1 
        self.puzzle = puzzle;
        self.x_range = range(0,width)
        self.y_range = range(0,height)
        self.i = 0

    def find_start(self):
        for x in self.x_range:
            for y in self.y_range:
                if (self.puzzle[x][y] == -1):
                    self.open_table.append(((x,y),-1))

    def xfs_step(self,pos,father):
        for step in self.move_method:
            x,y = (pos[0]+step[0],pos[1]+step[1])
            if (x in self.x_range and y in self.y_range):
                if (self.puzzle[x][y] == self.access):
                    flag = False
                    if (x,y) in (pos for _,pos,_ in self.closed_table):
                        flag = True
                    if (not flag): 
                        self.open_table.append(((x,y),father))
                elif (self.puzzle[x][y]==self.end):
                    self.open_table.append(((x,y),father))
                    return True
        return False
    
    def output(self):
        i,pos,father = self.closed_table.pop(-1)
        output_list = []
        output_list.insert(0,pos)
        while (not father == -1):
            i,pos,f = self.closed_table.pop(-1)
            if (i==father):
                output_list.insert(0,pos)
                father = f
        print(output_list)

    def run(self):
        self.find_start()
        while(len(self.open_table)>0):
            pos,father = self.open_table.pop(self.X)
            self.closed_table.append((self.i,pos,father))
            status = self.xfs_step(pos,self.i)
            self.i+=1
            if status:
                pos,father = self.open_table.pop()
                self.closed_table.append((self.i,pos,father))
                #print (self.closed_table)
                self.output()
                return True
        print('No valid access.')
        return False

puzzle = [
    [-1,1,0,0,0],
    [ 0,1,0,1,0],
    [ 0,0,0,0,0],
    [ 0,1,1,1,0],
    [ 0,0,0,1,2]
]

bfs_object = XFS('D',puzzle,5,5)
bfs_object.run()